package com.yanceysong.codetop.s41_s50;

import java.util.Deque;
import java.util.LinkedList;


public class S43_Easy_232_用栈实现队列 {
    // 输入栈: 负责接收新元素 (栈顶作为队尾)
    private final Deque<Integer> stackIn;
    // 输出栈: 负责提供队首元素 (栈顶作为队首)
    private final Deque<Integer> stackOut;

    /**
     * 用栈实现队列
     * 题目链接: <a href="https://leetcode.cn/problems/implement-queue-using-stacks/">...</a>
     * ------------------------------------------------------------------
     * 题目描述:
     * 仅使用两个栈实现一个先进先出 (FIFO) 的队列, 支持 push(x), pop(), peek(), empty()。
     * 只能使用栈的标准操作: push 进栈、pop 出栈、peek 顶元素、size、isEmpty。
     * ------------------------------------------------------------------
     * 示例:
     * 输入:
     * . MyQueue queue = new MyQueue();
     * . queue.push(1); // 队列: [1]
     * . queue.push(2); // 队列: [1,2]
     * . queue.peek();  // 返回 1  (队首仍为1)
     * . queue.pop();   // 返回 1, 队列: [2]
     * . queue.empty(); // 返回 false
     * ------------------------------------------------------------------
     * 核心思路 (Key Insight):
     * 使用两个栈: 输入栈 inStack(负责入队), 输出栈 outStack(负责出队和取队首)。
     * 当需要 pop / peek 且 outStack 为空时, 将 inStack 里的元素逐个弹出并压入 outStack。
     * 这样元素顺序被反转一次, 最早进入队列的元素转移后位于 outStack 顶部, 满足 FIFO。
     * 之后连续的 pop / peek 无需再次搬运 (形成摊还 / amortized O(1) 时间)。
     * ------------------------------------------------------------------
     * ASCII 流程图 (以 push(1), push(2), push(3), pop() 为例)
     * 初始: in=[], out=[]
     * push 1: in=[1], out=[]
     * push 2: in=[1,2], out=[]  (栈顶在右)
     * push 3: in=[1,2,3], out=[]
     * pop():  out 为空 => 搬运
     * .  搬运顺序: 3 -> out=[3]; in=[1,2]
     * .           2 -> out=[3,2]; in=[1]
     * .           1 -> out=[3,2,1]; in=[]
     * 现在 out 栈顶=1 -> 弹出得到 1 (队首)
     * 后续再 pop/peek 若 out 非空则直接操作，无需再次搬运。
     * ------------------------------------------------------------------
     * 时间复杂度分析:
     * - push: O(1)
     * - pop: 摊还 O(1) (一次元素最多被搬运 2 次: 进 in 一次 + 搬到 out 一次)
     * - peek: 摊还 O(1)
     * - empty: O(1)
     * 空间复杂度: O(n)  (n 为已入队元素总数)
     * ------------------------------------------------------------------
     * 设计要点 / 细节:
     * 1. 只有在 outStack 为空且需要读取队首(pop/peek)时才触发搬运, 避免重复反转。
     * 2. 不需要在每次 push 后都搬运; 这样可以延迟成本, 保证摊还效率。
     * 3. LeetCode 题目默认调用者不会在空队列上执行 pop/peek; 若生产环境需防御性校验可自行加异常处理。
     * 4. 可扩展: size 变量或方法, 直接返回 inStack.size + outStack.size。
     * ------------------------------------------------------------------
     * 对比真实队列:
     * 真实队列: 头部出, 尾部进。此实现: 通过一次整体反转再保持顺序, 达到相同语义。
     * ------------------------------------------------------------------
     */
    public S43_Easy_232_用栈实现队列() {
        stackIn = new LinkedList<>();
        stackOut = new LinkedList<>();
    }

    /**
     * 将元素 x 推到队列尾部
     * 直接压入输入栈即可, O(1)
     */
    public void push(int x) {
        stackIn.push(x);
    }

    /**
     * 弹出并返回队首元素
     * 如果输出栈为空, 先将输入栈全部倒入输出栈, 再弹出。
     */
    public int pop() {
        if (stackOut.isEmpty()) {
            transferInToOut(); // 触发一次整体反转
        }
        return stackOut.pop();
    }

    /**
     * 返回队首元素 (不移除)
     */
    public int peek() {
        if (stackOut.isEmpty()) {
            transferInToOut();
        }
        return stackOut.peek();
    }

    /**
     * 判断队列是否为空
     */
    public boolean empty() {
        return stackIn.isEmpty() && stackOut.isEmpty();
    }

    /**
     * 将 stackIn 中所有元素倒入 stackOut (一次性反转顺序)
     * 仅在 stackOut 为空时调用, 保障摊还复杂度。
     */
    private void transferInToOut() {
        while (!stackIn.isEmpty()) {
            stackOut.push(stackIn.pop());
        }
    }

    // ========================== 测试入口 ==========================
    public static void main(String[] args) {
        System.out.println("=== 用两个栈实现队列 测试开始 ===");

        System.out.println("\n--- 测试1: 题目示例基本功能 ---");
        testBasicExample();

        System.out.println("\n--- 测试2: 多次混合入队出队 ---");
        testInterleavedOperations();

        System.out.println("\n--- 测试3: 连续出队直到空 ---");
        testDequeueUntilEmpty();

        System.out.println("\n--- 测试4: 大量数据压力 + 摊还复杂度 ---");
        testStress();

        System.out.println("\n--- 测试5: 仅一次搬运验证 (集中 push, 然后全部 pop) ---");
        testSingleTransferScenario();

        System.out.println("\n--- 测试6: 交替 push/pop 验证延迟搬运策略 ---");
        testAlternatePushPop();

        System.out.println("\n=== 所有测试执行结束 (若无断言失败则全部通过) ===");
    }

    // ========================== 各测试用例实现 ==========================

    /**
     * 题目示例
     */
    private static void testBasicExample() {
        S43_Easy_232_用栈实现队列 queue = new S43_Easy_232_用栈实现队列();
        queue.push(1); // [1]
        queue.push(2); // [1,2]
        int peek1 = queue.peek();
        System.out.println("peek() -> " + peek1 + " (期望:1)");
        assert peek1 == 1;
        int pop1 = queue.pop();
        System.out.println("pop() -> " + pop1 + " (期望:1)");
        assert pop1 == 1;
        boolean empty = queue.empty();
        System.out.println("empty() -> " + empty + " (期望:false)");
        assert !empty;
    }

    /**
     * 多次混合操作
     */
    private static void testInterleavedOperations() {
        S43_Easy_232_用栈实现队列 q = new S43_Easy_232_用栈实现队列();
        q.push(10); // [10]
        q.push(20); // [10,20]
        assert q.peek() == 10;
        q.push(30); // [10,20,30]
        assert q.pop() == 10; // 剩 [20,30]
        q.push(40); // [20,30,40]
        assert q.pop() == 20; // [30,40]
        assert q.peek() == 30;
        q.push(50); // [30,40,50]
        assert q.pop() == 30; // [40,50]
        assert q.pop() == 40; // [50]
        assert q.pop() == 50; // []
        assert q.empty();
        System.out.println("混合操作全部断言通过");
    }

    /**
     * 连续出队直到空
     */
    private static void testDequeueUntilEmpty() {
        S43_Easy_232_用栈实现队列 q = new S43_Easy_232_用栈实现队列();
        for (int i = 1; i <= 5; i++) q.push(i); // [1,2,3,4,5]
        for (int i = 1; i <= 5; i++) {
            int v = q.pop();
            System.out.println("pop -> " + v + " (期望:" + i + ")");
            assert v == i;
        }
        assert q.empty();
        System.out.println("连续出队测试通过");
    }

    /**
     * 压力测试 & 摊还复杂度直观验证
     */
    private static void testStress() {
        S43_Easy_232_用栈实现队列 q = new S43_Easy_232_用栈实现队列();
        int n = 10000; // 适中数量, 证明不会超时
        for (int i = 0; i < n; i++) q.push(i);
        for (int i = 0; i < n; i++) {
            int val = q.pop();
            assert val == i;
        }
        assert q.empty();
        System.out.println("压力测试通过 (0.." + (n - 1) + ")");
    }

    /**
     * 只发生一次搬运的场景: 先全部 push 再全部 pop
     */
    private static void testSingleTransferScenario() {
        S43_Easy_232_用栈实现队列 q = new S43_Easy_232_用栈实现队列();
        q.push(5);
        q.push(6);
        q.push(7);
        // 第一次 pop 触发搬运, 之后的 pop 不再搬运
        assert q.pop() == 5;
        assert q.pop() == 6;
        assert q.pop() == 7;
        assert q.empty();
        System.out.println("单次搬运场景验证通过");
    }

    /**
     * 交替 push/pop 展示延迟搬运的好处
     */
    private static void testAlternatePushPop() {
        S43_Easy_232_用栈实现队列 q = new S43_Easy_232_用栈实现队列();
        q.push(1);            // in=[1]
        q.push(2);            // in=[1,2]
        assert q.pop() == 1;  // 触发搬运, out=[2]
        q.push(3);            // in=[3], out=[2]
        q.push(4);            // in=[3,4]
        assert q.pop() == 2;  // out 直接弹出
        assert q.pop() == 3;  // 触发第二次搬运 (in->[4])
        assert q.peek() == 4; // 查看剩余
        assert q.pop() == 4;  // 为空
        assert q.empty();
        System.out.println("交替 push/pop 测试通过");
    }
}
